1
Princípios da Minimização Irrestrita
MATH008Lesson 9
00:00
Passamos da existência teórica de um mínimo para o mecanismo algorítmico da otimização. Nosso objetivo principal é minimizar $f(x)$ (9.1) onde $f: \mathbf{R}^n \to \mathbf{R}$ é convexa e duas vezes continuamente diferenciável. Como $f$ é diferenciável e convexa, uma condição necessária e suficiente para que um ponto $x^*$ seja ótimo é $\nabla f(x^*) = 0$.

O Framework Algorítmico

Soluções numéricas constroem uma sequência de minimização: Uma sequência de pontos $x^{(0)}, x^{(1)}, \dots \in \text{dom } f$ com $f(x^{(k)}) \to p^*$ quando $k \to \infty$. Cada passo atualiza a posição por meio de $x^{(k+1)} = x^{(k)} + t^{(k)}\Delta x^{(k)}$, onde $\Delta x$ é uma direção de descida.

Inicialização e Convergência

Os métodos descritos neste capítulo exigem um ponto inicial adequado $x^{(0)}$. O ponto inicial deve estar em $\text{dom } f$, além disso, o conjunto de nível inferior $S = \{x \in \text{dom } f \mid f(x) \le f(x^{(0)})\}$ deve ser fechado. Isso garante que a sequência permaneça em uma região bem comportada onde o hessiano fornece informações úteis.

Direções de Descida

A direção mais simples é $\Delta x = -\nabla f(x)$. No entanto, a eficiência muitas vezes exige considerar diferentes geometrias através da direção de descida mais íngreme:

  • Norma Quadrática: $\|z\|_P = (z^T P z)^{1/2} = \|P^{1/2}z\|_2$.
  • Norma $L_\infty$: $\Delta x_{\text{sd}} = \Delta x_{\text{nsd}} \|\nabla f(x)\|_\infty = - \frac{\partial f(x)}{\partial x_i} e_i$ (Descida por Coordenadas).

Modelos de Segunda Ordem e Regiões de Confiança

O método de Newton utiliza uma aproximação de Taylor de segunda ordem: $$\hat{f}(x+v) = f(x) + \nabla f(x)^T v + \frac{1}{2} v^T \nabla^2 f(x) v$$ Esta quadrática é minimizada quando $v = \Delta x_{nt}$ (passo de Newton). Definimos uma região de confiança: o conjunto $\{v \mid \|v\|_2 \le \gamma\}$. O parâmetro $\gamma$ reflete nossa confiança no modelo de segunda ordem. Quando o modelo é preciso, resolvemos a direção por meio de $v = L^{-T}w = -L^{-T}L^{-1}P^T g$ nos sistemas KKT.

🎯 Princípios Fundamentais de Convergência
A eficiência é medida pela velocidade com que o erro $f(x^{(k)}) - p^*$ desaparece. Para funções fortemente convexas, o erro $f(x^{(k)}) - p^*$ converge para zero pelo menos tão rápido quanto uma série geométrica. No contexto de métodos numéricos iterativos, isso é chamado de convergência linear.
  • Limite de Subotimalidade: $p^* \geq f(x) + \lambda(x) + \log(1 - \lambda(x))$, válido se $\lambda(x) < 1$.
  • Soma de Auto-Concordância: Se $f_1, f_2$ forem auto-concordantes, então $f_1 + f_2$ também é auto-concordante.
  • Esparsidade do Hessiano: A eficiência é obtida se a condição de estrutura de banda do hessiano: $\nabla^2 f(x)_{ij} = 0$ para $|i-j| > k$ for verdadeiro.